package isnork.g3;

import isnork.sim.SeaLifePrototype;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.TreeMap;

/**
 * Refined direction angles
 */
enum DirectionAngle {

	N(90, 0, 1), S(270, 0, -1), W(180, -1, 0), E(0, 1, 0), NE(45, 1, 1), NW(
			135, -1, 1), SE(315, 1, -1), SW(225, -1, -1), NNE(68, 0.37, 0.92), NEE(
			23, 0.92, 0.39), NNW(113, -0.39, 0.92), NWW(158, -0.92, 0.37), SWW(
			203, -0.92, -0.39), SSW(248, -0.37, -0.92), SEE(338, 0.92, -0.37), SSE(
			293, 0.39, -0.92);

	int deg;
	double dx, dy;

	private DirectionAngle(int degrees, double x, double y) {
		this.deg = degrees;
		this.dx = x;
		this.dy = y;
	}

}

class Message {
	// Direction direction = null;
	DirectionAngle directionAngle = null;
	SeaLifePrototype slp;
	int r;
	int id;
	int freq;
	boolean isTracking = false;

	public Message(SeaLifePrototype slp, int r, int freq, DirectionAngle angle,
			int id) {
		// this.directionAngle = angle;
		this.slp = slp;
		this.r = r;
		this.freq = freq;
		this.isTracking = false;
		this.id = id;
	}

	public Message(SeaLifePrototype slp, int id) {
		this.slp = slp;
		this.id = id;
		this.isTracking = true;
	}

	public boolean equals(Object o) {
		if (o instanceof Message) {
			Message c = (Message) o;
			if (
			// (this.r == c.r)
			// && ((this.direction == null) || (c.direction == null) ||
			// (this.direction == c.direction))
			// &&
			// ((this.directionAngle == null)
			// || (c.directionAngle == null) || (this.directionAngle ==
			// c.directionAngle))
			// &&
			this.slp.getName().equals(c.slp.getName()) && (this.id == c.id)) {
				return true;
			}
		}
		return false;

	}

	public int hashCode() {
		return (this.slp.hashCode() + this.id);
	}
}

class HuffmanNode {
	HuffmanNode nodes[];

	String c; 	// The character of this node
	int freq; 	// The frequency
	int n; 		// The number of children

	public HuffmanNode(int n) {
		this.n = n;
		nodes = new HuffmanNode[n];
	}

}

public class EncodedCommunication {

	TreeMap<Integer, LinkedList<Message>> messages;

	TreeMap<Integer, LinkedList<HuffmanNode>> nodes;
	private HuffmanNode hTree = null;

	HashMap<Message, String> msgs = new HashMap<Message, String>();
	HashMap<String, Message> rmsgs = new HashMap<String, Message>();
	HashMap<Integer, LinkedList<String>> table = new HashMap<Integer, LinkedList<String>>();

	private Set<SeaLifePrototype> slpPrototypes = new HashSet<SeaLifePrototype>();

	private static int nALPHABET = 26;

	public EncodedCommunication(Set<SeaLifePrototype> slps, int r) {

		messages = new TreeMap<Integer, LinkedList<Message>>();
		nodes = new TreeMap<Integer, LinkedList<HuffmanNode>>();

		this.slpPrototypes = slps;

		// Build the messages encodings
		for (SeaLifePrototype slp : this.slpPrototypes) {
			// for (DirectionAngle d : DirectionAngle.values())
			{
				// for (int i = 0; i <= r; i++)
				{
					for (int q = 0; q < slp.getMaxCount(); q++) {
						Message m = new Message(slp, 0,
								(slp.getMinCount() + slp.getMaxCount()) / 2
										+ slp.getHappiness(), null, q);
						if (messages.containsKey(m.freq)) {
							messages.get(m.freq).add(m);
							HuffmanNode n = new HuffmanNode(nALPHABET);
							n.freq = m.freq;
							nodes.get(m.freq).add(new HuffmanNode(nALPHABET));
							// j++;
						} else {
							LinkedList<Message> l = new LinkedList<Message>();
							l.add(m);
							messages.put(m.freq, l);
							LinkedList<HuffmanNode> n = new LinkedList<HuffmanNode>();
							HuffmanNode nd = new HuffmanNode(nALPHABET);
							nd.freq = m.freq;
							n.add(nd);
							nodes.put(m.freq, n);
							// j++;
						}
					}
				}

			}
		}
	}

	int getHashedValue(int max, int id) {
		return id % max;
	}

	public int dfs(HuffmanNode tree, String s) {
		for (int i = 0; i < nALPHABET; i++) {
			if (tree.nodes[i] != null) {
				s += tree.nodes[i].c;
				dfs(tree.nodes[i], s);
				s = s.substring(0, s.length() - 1);
			} else {
				if (!s.equals("") && tree.freq != 0) {
					// GameEngine.println("s " + s + " f" + tree.freq);
					if (this.table.containsKey(tree.freq)) {
						this.table.get(tree.freq).add(s);
					} else {
						LinkedList<String> li = new LinkedList<String>();
						li.add(s);
						this.table.put(tree.freq, li);
					}

				}
				break;
			}

		}
		return 0;
	}

	public void buildTree() {
		HuffmanNode node = new HuffmanNode(nALPHABET);

		int sumFreq = 0;
		char c = 'a'; // First character of the alphabet
		for (int i = 0; i < nALPHABET; i++) {
			if (this.nodes.isEmpty()) {
				node.nodes[i] = null;
				break;
			}
			int key = this.nodes.firstKey();
			sumFreq += key;
			node.nodes[i] = this.nodes.get(key).getFirst();
			if (node.c == null) {
				node.nodes[i].c = new String();
				node.nodes[i].c += c;
			} else {
				node.nodes[i].c = node.c + c;
			}
			node.nodes[i].freq = key;
			if (this.nodes.get(key).size() == 1)
				this.nodes.remove(key);
			else
				this.nodes.get(key).remove(0);
			c++;
		}

		if (!this.nodes.isEmpty()) {
			if (this.nodes.containsKey(sumFreq)) {
				this.nodes.get(sumFreq).add(node);
			} else {
				LinkedList<HuffmanNode> n = new LinkedList<HuffmanNode>();
				n.add(node);
				this.nodes.put(sumFreq, n);
			}
			this.buildTree();
		} else {
			this.hTree = node;
			this.dfs(hTree, new String());
			int len = 0;
			double avLen = 0;
			int k = 0;
			for (Integer i : this.table.keySet()) {
				int j = 0;
				for (String s : this.table.get(i)) {
					if (s.length() > len)
						len = s.length();
					avLen += s.length();
					k++;
					Message tmsg = this.messages.get(i).get(j);
					j++;
					this.rmsgs.put(s, tmsg);
					this.msgs.put(tmsg, s);
				}
			}
			avLen /= k;
		//	if (SimpleUtil.DEBUG)
		//		GameEngine.println("Maximum length of encoded word " + len
		//				+ " Average length " + avLen);
			return;
		}

	}

	public String getEncodedString(Message m) {
		return this.msgs.get(m);
	}

	public Message getDecodedString(String encoded) {
		if (encoded == null)
			return null;
		return this.rmsgs.get(encoded);
	}

}
